const {
  TreeNode,
  genTree,
  printTree
} = require('../data_structure/tree_node.js')

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} limit
 * @return {TreeNode}
 */
var sufficientSubset2 = function (root, limit) {
  let height = Math.ceil(Math.log2(root.length))
  let k = height
  let res = [...root]
  let sumFn = idx => {
    if (root[idx] === null) return limit - 1
    let res = 0
    let parent = idx
    while (parent >= 0) {
      res += root[parent] || 0
      parent = Math.floor((parent - 1) / 2)
    }
    return res
  }
  while (height > 0) {
    for (
      let i = Math.pow(2, height - 1) - 1;
      i < Math.pow(2, height) - 1 && i < root.length - 1;
      i += 2
    ) {
      if (
        height === k ||
        (res[i * 2 + 1] === undefined &&
          res[i * 2 + 2] === undefined &&
          res[i] != undefined)
      ) {
        let left = sumFn(i)
        let right = sumFn(i + 1)
        if (left < limit && right < limit) {
          res[i] = undefined
          res[i + 1] = undefined
          res[(i - 1) / 2] = undefined
        } else if (left < limit) {
          res[i] = undefined
        } else if (right < limit) {
          res[i + 1] = undefined
        }
      }
    }
    height -= 1
  }
  return res
}

var sufficientSubset = function (root, limit) {
  let haveSufficient = checkSufficientLeaf(root, 0, limit)
  return haveSufficient ? root : null
}
var checkSufficientLeaf = function (node, prevSum, limit) {
  if (node === null) {
    return false
  }
  if (node.left === null && node.right === null) {
    return node.val + prevSum >= limit
  }
  let haveSufficientLeft = checkSufficientLeaf(
    node.left,
    node.val + prevSum,
    limit
  )
  let haveSufficientRight = checkSufficientLeaf(
    node.right,
    node.val + prevSum,
    limit
  )
  if (!haveSufficientLeft) {
    node.left = null
  }
  if (!haveSufficientRight) {
    node.right = null
  }
  return haveSufficientLeft || haveSufficientRight
}
let root = [1, 2, 3, 4, -99, -99, 7, 8, 9, -99, -99, 12, 13, -99, 14]
let limit = 1

// root = [1, 2, -3, -5, null, 4, null]
// limit = -1

// root = [5, 4, 8, 11, null, 17, 4, 7, 1, null, null, 5, 3]
// limit = 22
let t = genTree(root)
console.log(printTree(t))
console.log(printTree(sufficientSubset(t, limit)))
